package com.wc.alorithm_luogu.P2758_编辑距离;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/3/15 15:29
 * @description https://www.luogu.com.cn/problem/P2758
 */
public class Main {
    static char[] s1 = new char[1];
    static char[] s2 = new char[1];
    static int N = 2010;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s1 = (" " + sc.next()).toCharArray();
        s2 = (" " + sc.next()).toCharArray();
        for (int i = 0; i < N; i++) {
            Arrays.fill(f[i], -1);
        }
        int len1 = s1.length - 1;
        int len2 = s2.length - 1;
        System.out.println(dp(len1, len2));
    }

    static int dp(int i, int j) {
        // 如果当前位置计算过，就不需要计算了
        if (f[i][j] != -1) return f[i][j];
        // i == 0,说明走到头了，就只能增加j个
        if (i == 0) return f[i][j] = j;
        // j == 0,说明走到头了，就只能删除i个
        if (j == 0) return f[i][j] = i;
        int val = 1;
        if (s1[i] == s2[j]) val = 0;
        // 删除，dp(i - 1, j) + 1,将最末尾的数字删除
        // 增加，dp(i, j - 1) + 1,在i后面添加一个，相当于在j后面的数字删除
        // 修改，dp(i - 1,j - 1) + val, s1[i] == s2[j]相等是不需要修改的
        return f[i][j] = Math.min(dp(i - 1, j) + 1, Math.min(dp(i, j - 1) + 1, dp(i - 1, j - 1) + val));
    }
}

